package 剑指offer;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:55:02 
* @Description：
* 
统计一个数字在排序数组中出现的次数。
*/
public class A37数字在排序数组当中出现的次数 {
//数组是有序的，用二分查找
	public static int GetNumberOfK(int [] array , int k) {
			int length = array.length;
			        if(length == 0){
			            return 0;
			        }
			        int firstK = getFirstK(array, k, 0, length-1);
			        int lastK = getLastK(array, k, 0, length-1);
			        if(firstK != -1 && lastK != -1){
			             return lastK - firstK + 1;
			        }
			        return 0;
			    }
			    //递归写法
			    private static int getFirstK(int [] array , int k, int start, int end){
			        if(start > end){
			            return -1;
			        }
			        int mid = (start + end) >> 1;
			        if(array[mid] > k){
			            return getFirstK(array, k, start, mid-1);
			        }else if (array[mid] < k){
			            return getFirstK(array, k, mid+1, end);
			        }else if(mid-1 >=0 && array[mid-1] == k){
			            return getFirstK(array, k, start, mid-1);
			        }else{
			            return mid;
			        }
			    }
			    //循环写法
			    private static  int getLastK(int [] array , int k, int start, int end){
			        int length = array.length;
			        int mid = (start + end) >> 1;
			        while(start <= end){
			            if(array[mid] > k){
			                end = mid-1;
			            }else if(array[mid] < k){
			                start = mid+1;
			            }else if(mid+1 < length && array[mid+1] == k){
			                start = mid+1;
			            }else{
			                return mid;
			            }
			            mid = (start + end) >> 1;
			        }
			        return -1;
			    }
			 
public static int GetNumberOfK11(int [] array , int k) {
	HashMap<Integer,Integer> map = new HashMap<>();
	if (array==null ) {
		return -1;
	}else if (array.length==1) {
		return array[0];
	}
	
	for(int i=0;i<array.length;i++) {
		if (map.containsKey(array[i])) {
			Integer count = map.get(array[i]);
			map.put(array[i], ++count);
		}else {
			map.put(array[i], 1);
		}
	}
	int res=0;
	Iterator<Integer> iterator = map.keySet().iterator();
	while(iterator.hasNext()) {
		Integer key = iterator.next();             //这里取出来的key
		if (key==k) {
			return res=map.get(key);             //这里取出来的是key值对应的value
		}
	}
	return res;
}
			    
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String s = scanner.nextLine();
		String[] ss = s.split(" ");
		int [] arr=new int [ss.length];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=Integer.parseInt(ss[i]);
		}
		int k = scanner.nextInt();
		int numberOfK = GetNumberOfK(arr, k);
		System.out.println(numberOfK);
		int ofK11 = GetNumberOfK11(arr, k);
		System.out.println(ofK11);
	}
}
